package problem.year2021.january;

import java.util.HashSet;
import java.util.Set;

/**
 * Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3  种类型的边：
 * <p>
 * 类型 1：只能由 Alice 遍历。
 * 类型 2：只能由 Bob 遍历。
 * 类型 3：Alice 和 Bob 都可以遍历。
 * 给你一个数组 edges ，其中 edges[i] = [typei, ui, vi] 表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。
 * <p>
 * 返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
 * <p>
 * 1 <= n <= 10^5
 * 1 <= edges.length <= min(10^5, 3 * n * (n-1) / 2)
 * edges[i].length == 3
 * 1 <= edges[i][0] <= 3
 * 1 <= edges[i][1] < edges[i][2] <= n
 * 所有元组 (typei, ui, vi) 互不相同
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * <p>
 * 解题思路，分类讨论，最先操作的应该是将图中所有类型的边分割开来，然后分类讨论；
 */
public class January27 {
    public int maxNumEdgesToRemove(int n, int[][] edges) {
        // 第一步，判断这个图构成遍历条件吗；N个点至少需要n-1条边才能构成完全遍历
        if (n == 1 || n - 1 > edges.length) return -1; // n = 1表示只有一个点，图都构不成，还删除个屁啊
        // 第二步：分类讨论，构建两个图Alice和Bob渐入点集合
        Set<Integer> alice = new HashSet<>();
        Set<Integer> bob = new HashSet<>();
        int p = 0;
        UnionFind al = new UnionFind(n);
        UnionFind bo = new UnionFind(n);
        for (int[] e : edges) {
            if (e[0] == 3) {
                // 如果两个点集合都包含，则证明这条边是多余的
                if (alice.contains(e[1]) && alice.contains(e[2]) && bob.contains(e[1]) && bob.contains(e[2])) {
                    ++p;
                    continue;
                }
                alice.add(e[1]);
                alice.add(e[2]);
                bob.add(e[1]);
                bob.add(e[2]);
                if (!al.union(e[1], e[2]) && !bo.union(e[1], e[2])) ++p;
            } else if (e[0] == 2) {
                if (bob.contains(e[1]) && bob.contains(e[2])) {
                    ++p;
                    continue;
                }
                bob.add(e[1]);
                bob.add(e[2]);
                if (!bo.union(e[1], e[2])) ++p;
            } else {
                alice.add(e[1]);
                alice.add(e[2]);
                if (!al.union(e[1], e[2])) ++p;
            }
        }
        if (alice.size() == n && bob.size() == n) return p; // 遍历这些点的基本要素是集合中有这么多的点，如果点数都不够，就直接清除
        return -1;
    }

    private class UnionFind {
        int[] parent;

        public UnionFind(int n) {
            parent = new int[n + 1];
            parent[0] = -1;
            for (int i = 1; i < parent.length; ++i) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parent[x] = parent[y];
                return true; // 表示合并成功，且已经合并
            }
            return false; // 表示合并失败，两个本来就是一个集合的
        }
    }

    public static void main(String[] args) {
        // n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
        // result = 2
        // n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
        // result = 0
        System.out.println(new January27().maxNumEdgesToRemove(4, new int[][]{{3, 1, 2}, {3, 2, 3}, {1, 1, 3}, {1, 2, 4}, {1, 1, 2}, {2, 3, 4}}));
        System.out.println(new January27().maxNumEdgesToRemove(4, new int[][]{{3, 1, 2}, {3, 2, 3}, {1, 1, 4}, {2, 1, 4}}));
    }
}
